1. Field of the Invention
The present invention relates to a data queuing apparatus. More specifically, the present invention relates to a data queuing apparatus for controlling addresses of data switching apparatus or a common buffer type data switching apparatus used for temporarily storing, delaying and switching a limited length of data, such as a fixed length packets and block frame information of various kinds of multimedia, for example, voice, data, image and so on.
2. Description of the Background Art
In ATM (Asynchronous Transfer Mode) communication systems, continuous signals such as line signals or voice signals, and bursty signals such as data signal and motion pictures are divided into fixed length of data, appended to a routing header indicative of destination information, for example, and thus a packet is formed. Information is transferred in the same packet form. Synchronization of frame or the like between a terminal and a transmission channel becomes unnecessary, and the operating speed of the terminal equipment and the transmission channel can be set independently. Therefore, the system can be applied to any terminal equipment. However, in a high speed packet switch, packets arrive at random. Therefore, it is possible that a plurality of packets are addressed to one destination at one time, and therefore it becomes necessary for queuing the packets in order to prevent loss of information.
To solve this problem, for example, high speed packet switch is proposed and shown in FIGS. 5 and 6 of International Conference on Communications, 1987, session 22, Document No. 2, Jean-Pierre Coudreuse, Michel Sorvel, "PRELUDE: Asynhcronous Time-Division Switched Network". This document relates to a high speed packet switch of an asynchronous transfer mode (ATM) communication system for efficiently multiplexing and transmitting line switching data or packet switching data. A conventional data queuing apparatus is shown in a control circuit therein.
FIG. 42 is a block diagram showing a conventional high speed packet switch including a data queuing apparatus. Referring to FIG. 42, input lines 111 to 11m are for inputting m (m.gtoreq.2) data to a packet multiplexing circuit 13. The packet input through input lines 111 to 11m has a fixed length. Packet multiplexing circuit 13 multiplexes the input packets, and it applies arrived routing headers to a control circuit 16 and applies the packets to a memory 14. Data can be written to a designated address of memory 14, and data can be read independent from the order of writing, by designating an address. The data read from memory 14 is applied to a packet demultiplexing circuit 15 in which read packets are demultiplexed and output to output lines 121 to 12m. Control circuit 16 controls packet exchange.
FIG. 43 is a block diagram showing details of the control circuit shown in FIG. 42. Control circuit 16 includes data queuing apparatus disclosed in FIG. 10 of the aforementioned article, in schematic representation for simplicity of description. Referring to FIG. 43, control circuit 16 includes a header exchanging circuit 17 and a cyclic selector 20. Header exchanging circuit 17 determines, based on the routing header of the arrived packet, the address of memory 14 to which the packet is written, determines which of the output lines 121 to 12m is the destination of the packet, and exchanges the header with a new routing header. Cyclic selector 20 selects information in order. To data queuing apparatus 18, a write address signal to memory 14 is input through input line 1, and packet destination is input through destination designating input lines 31-3m. Packets are output through output lines 21 to 2m after queuing of addresses. Data queuing apparatus 18 includes memories 191 to 19m provided corresponding to output lines 121 to 12m, respectively. Data queuing apparatus 18 arranges write address signals of the arrived packets in correspondence to output lines 21 to 2m, respectively, thus forming a queue, and output address signals in the order of arrival, from each of the output lines 121 to 12m.
The packets which have arrived at the plurality of input lines 111 to 11m of the high speed packet switch shown in FIG. 42 are multiplexed by packet multiplexing circuit 13 and written to memory 14. The routing header including destination information of the arrived packet is applied to control circuit 16, in which header exchanging circuit 17 determines which of destination output lines 121 to 12m is the destination, and the header is exchanged with a new routing header. Addresses written in memory 14 are turned into queues corresponding to respective ones of destination output lines 121 to 12m by data queuing apparatus 18. First In First Out (FIFO) memories 191 to 19m are used in the data queuing apparatus 18.
Meanwhile, in accordance with the addresses read from data queuing apparatus 18, packets are read from memory 14, demultiplexed by packet demultiplexing circuit 15, and the packets are output to prescribed output lines 121 to 12m. By the above described operation of the data queuing apparatus 18, packets on the input lines 111 to 11m are provided on the desired output lines 121 to 12m, and thus packet exchange is realized.
Since the conventional data queuing apparatus has been structured as described above, when memory 14 has the write capacity of P packets, for example, it is necessary for each of the FIFO memories 191 to 19m to have sufficient capacity for holding P addresses, in order to prevent information loss caused by address overflow. This means that data queuing apparatus 18 as a whole must have the address holding capacity of P.times.m, which results in large scale apparatus.
Meanwhile, the inventors of the present application have proposed in U.S. patent application Ser. No. 191,335, now U.S. Pat. No. 5,504,741, a data queuing apparatus which is capable of reducing the scale of the apparatus as a whole by making smaller the memory capacity, and which is also capable of reducing ratio of disposal of data caused by memory capacity overflow by sharing a memory holding data queue by all the output lines without the necessity of providing a plurality of memories for holding the data queue.